﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace seiacpscs_a2.datastructures.tree
{
    public class BinarySearchTreeRecursive : DataStructure
    {
        private TreeNode rootNode;
        private int size;

        public int Size
        {
            get { return size; }
        }

      


        public BinarySearchTreeRecursive()
        {
        }

        public void addItems(params int[] items)
        {
            items.ToList().ForEach(x => add(x));
        }

        public override void add(int item)
        {
            if (this.rootNode == null)
            {
                this.rootNode = new TreeNode(item, null, null);
                size++;
            }
            else
            {
                insert(this.rootNode, item);
            }
        }

        private void insert(TreeNode node, int item)
        {
            if (node == null)
                return;

            if (item == node.Item)
                return;
            else if (item < node.Item)
            {
                if (node.Left == null)
                {
                    node.Left = new TreeNode(item, null, null);
                    size++;
                }
                else
                {
                    insert(node.Left, item);
                }
            }
            else
            {
                if (node.Right == null)
                {
                    node.Right = new TreeNode(item, null, null);
                    size++;
                }
                else
                {
                    insert(node.Right, item);
                }
            }

        }

        public override bool contains(int item)
        {
            this.numberOfAccesses = 0;
            Boolean isFound = false;

            if (this.rootNode == null)
                return isFound;

            isFound = contains(item, this.rootNode);
            return isFound;
        }

        private Boolean contains(int item, TreeNode node)
        {
            if (node == null)
            {
                ++(this.numberOfAccesses);
                return false;
            }

            if (item < node.Item)
            {
                ++(this.numberOfAccesses);
                return contains(item, node.Left);
            }
            else if (item > node.Item)
            {
                ++(this.numberOfAccesses);
                return contains(item, node.Right);
            }
            else
            {
                ++(this.numberOfAccesses);
                return true;
            }
        }

        public override string DataStructureName
        {
            get { return "Binary Search Tree"; }
        }
    }
}
